A primary goal in digital communications is the transmission of data in error-free form. During transmission, the data is subjected to noise which may cause errors in the received data. To improve the reliability of data transmission, one of a variety of possible error correction techniques is commonly utilized. A known error correction technique is convolutional coding. This technique provides an effective error correction capability but requires sophisticated decoding techniques.
An optimal solution for decoding convolutional codes is credited to Andrew Viterbi and is well known as the Viterbi algorithm (VA). The Viterbi algorithm is a recursive solution to the problem of estimating the state sequence of a discrete-time finite-state Markov process observed in memory-less noise. Viterbi decoding is not restricted to convolutional codes, but can be applied to other sequence estimation problems such as channel equalizers. Decoding of convolutional codes requires making probabilistic decisions based on a sequence of received bits rather than on an individual bit-by-bit basis. The basic operation of the Viterbi decoder is to select the path through a trellis, in the presence of noise, that represents the most likely sequence that was generated by a convolutional encoder. The Viterbi algorithm makes use of the recurrent properties of convolutional codes to provide an efficient solution to this problem. At each symbol period the algorithm generates a metric, a measure of probability, for each branch. The best path to each state is then determined by examining the accumulated metrics from all paths entering the state and selecting the one with the best metric. The other path or paths are discarded. Therefore, paths with errors will accumulate lower metrics and therefore be discarded leaving only the path that represents the sequence which was most likely generated by the encoder. To implement the Viterbi algorithm, a plurality of add/compare/select (ACS) operations must be performed to calculate the best path to each state. In today's central processing architectures which implement the Viterbi algorithm, sequential processing is utilized to perform the ACS operations. In a CPU approach, a plurality of sequential memory fetches, addition, storage and comparison operations must be executed. The sequential operation limits data throughput due to the high number of instructions needed per symbol or data bit. An alternative to this problem is the use of full or semi-parallel word-wide processing architectures. For example, a hardware circuit is implemented for each required state to perform the ACS operations in parallel. Because branch and path metrics are represented as multibit values, each ACS circuit must perform multibit arithmetic calculations. The parallel operation architectures require a large area of silicon to implement due to: (1) a large plurality of elements such as adders, comparators, etc. required for each state to implement word-wide processing; and (2) extensive interconnect resulting from the required use of multi-bit data buses.